/*
 * @lc app=leetcode.cn id=198 lang=cpp
 *
 * [198] 打家劫舍
 *
 * 方法1：动态规划
 * - 状态 dp[i]：到达第 i 间房屋所获取的最高金额
 * - 状态转移方程：dp[i] = max{dp[i-1], dp[j] + arr[i]} , j < i-1
 * - 使用大根堆获取 max{dp[j]} , j < i-1
 */

#include <vector>
#include <queue>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int rob(std::vector<int> &nums)
    {
        const int len = nums.size();
        if (len == 1)
            return nums[0];
        else if (len == 2)
            return std::max(nums[0], nums[1]);

        std::vector<int> amountDP(len); // 到达第 i 间房屋所获取的最高金额
        amountDP[0] = nums[0];
        amountDP[1] = nums[1];
        std::priority_queue<int> amountHeap; // 之前得到的最高金额

        for (int i = 2; i < len; i++)
        {
            /* dp[i] = max{dp[i-1], dp[j] + arr[i]} , j < i-1 */
            amountHeap.push(amountDP[i - 2]);
            amountDP[i] = std::max(amountDP[i - 1], amountHeap.top() + nums[i]);
        }

        return amountDP[len - 1];
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {2, 1, 1, 2};

    std::cout << solution.rob(nums) << std::endl;

    return 0;
}